package leetcode;

import leetcode.*;

/**
 * Created by tizzybec on 6/24/2016.
 */
public class Solution206 {
    // non recursive
    public ListNode reverseList(ListNode head) {
        if (head != null && head.next != null) {
            ListNode preNode = head;
            ListNode currNode = preNode.next;
            while (currNode != null) {
                ListNode nextNode = currNode.next;
                currNode.next =  preNode;
                preNode = currNode;
                currNode = nextNode;
            }
            head.next = null;
            return preNode;
        }
        return head;
    }

    private ListNode recursiveReverse(ListNode pre, ListNode next) {
        if (next != null) {
            ListNode n = next.next;
            next.next = pre;
            return recursiveReverse(next, n);
        } else {
            return pre;
        }
    }

    public ListNode reverseList2(ListNode head) {
        if (head != null) return recursiveReverse(null, head);
        return head;
    }
}
